package middle;

import java.util.ArrayList;
import java.util.List;

public class Solution_417 {

    public static void main(String[] args) {
        Solution_417 model = new Solution_417();
        System.out.println(model.pacificAtlantic(new int[][]{{10, 10, 10}, {10, 1, 10}, {10, 10, 10}}));
    }

    private int[][] directs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int r, c;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        r = heights.length;
        c = heights[0].length;
        boolean[][] a_array = new boolean[r][c];
        boolean[][] b_array = new boolean[r][c];
        for (int i = 0; i < c; i++) {
            dps(a_array, heights, 0, i);
            dps(b_array, heights, r - 1, i);
        }

        for (int i = 0; i < r; i++) {
            dps(a_array, heights, i, 0);
            dps(b_array, heights, i, c - 1);
        }

        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (a_array[i][j] && b_array[i][j]) {
                    List<Integer> tip = new ArrayList<>();
                    tip.add(i);
                    tip.add(j);
                    list.add(tip);
                }
            }
        }
        return list;
    }

    private void dps(boolean[][] visited, int[][] heights, int i, int j) {
        if (visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        for (int[] direct : directs) {
            int next_r = i + direct[0];
            int next_c = j + direct[1];
            if (next_r < 0 || next_r >= r || next_c < 0 || next_c >= c || heights[next_r][next_c] < heights[i][j]) {
                continue;
            }
            dps(visited, heights, next_r, next_c);
        }
    }
}
